package practises;

public class Num6 {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(2);
        head.next.next.next = new ListNode(1);
        Num6 n = new Num6();
        ListNode ret = n.partition(head, 2);

        while(ret != null) {
            System.out.print(ret.val + " ");
            ret = ret.next;
        }
        int k = 1;
    }
    public ListNode partition(ListNode pHead, int x) {
        if(pHead == null) {
            return null;
        }
        ListNode newHead = new ListNode(0);

        ListNode cur = pHead;//表示遍历链表的当前指针 也是最后一个节点
        ListNode newTail = newHead;//新链表的尾节点
        ListNode t;
        //大的尾插 小的头插 error
        //都应该尾插
        ListNode smallNewTail = newHead;//这个表示较小节点的最后一个
        boolean flag = false;
        while(cur != null) {
            t = cur.next;
            if(cur.val < x) {
                cur.next = smallNewTail.next;
                smallNewTail.next = cur;
                smallNewTail = smallNewTail.next;
                if(newTail == newHead) {
                   flag = true;
                }
            } else {
                if(flag) {
                    newTail = smallNewTail;
                    flag = false;
                }
                newTail.next = cur;
                newTail = newTail.next;
            }
            cur = t;
        }
        if(newTail != newHead) {
            newTail.next = null;
        }
        return newHead.next;
    }
}
